• Problem Statement
• Key Insight
• Code
• Conclusion

Codeforces Problem 1883B - Chemistry

Codeforces Round- 905A, Simplified Solution to "Can You Rearrange a String into a Palindrome After k Deletions?"

problem link: Codeforces Problem 1883B - Chemistry from Codeforces.

This blog focuses on solving the Codeforces "Chemistry" problem, where we are asked to determine whether it’s possible to rearrange a string into a palindrome after deleting exactly \( k \) characters. We’ll break the problem into simple, clear steps, explain the logic, and provide an efficient solution that works for large inputs.

Problem Statement

You are given:

• A string \( s \) of length \( n \), consisting of lowercase English letters.
• An integer \( k \), representing the number of characters you are allowed to delete.

You need to determine:

• Whether it’s possible to delete exactly \( k \) characters such that the remaining string can be rearranged into a palindrome.

What is a Palindrome?

A palindrome is a string that reads the same forwards and backwards. Examples: "abba", "racecar", "z" are palindromes, while "abc", "codeforces" are not palindromes.

Key Insight: Conditions for a Palindrome

To rearrange a string into a palindrome:

• All characters must appear an even number of times (if the palindrome’s length is even).
• If the palindrome’s length is odd, at most one character can appear an odd number of times.

Example:

• "aabb" → All characters appear even times → Palindrome.
• "aabbc" → 'c' appears once (odd) → Still valid as a palindrome because one character can have an odd frequency.

Simplified Thought Process

Instead of worrying about the palindrome structure in detail, we focus on:

1. Counting the characters that appear an odd number of times in the string.
2. Checking whether we can remove enough characters (within the allowed \( k \)) to make the string fit the palindrome conditions.

Key Observation:

If there are \( \text{oddCount} \) characters with odd frequencies, then:

• We need to delete at least \( \text{oddCount} - 1 \) characters to allow for a palindrome (we keep one odd character and make all others even).

Condition to Check:

If \( k \geq \text{oddCount} - 1 \), the answer is "YES". Otherwise, the answer is "NO".

Why \( \text{oddCount} - 1 \)?

The reasoning is simple:

We are allowed to keep one character with an odd frequency.

To achieve this, we must "fix" all other odd frequencies by deleting enough characters.

Thus, we only need \( \text{oddCount} - 1 \) deletions.

Steps to Solve the Problem

1. Count Character Frequencies: Use an array of size 26 to count how many times each letter appears.
2. Count Odd Frequencies: Loop through the frequency array and count the characters that appear an odd number of times (\( \text{oddCount} \)).
3. Check the Condition: If \( k \geq \text{oddCount} - 1 \), print "YES". Otherwise, print "NO".

Code Implementations

Below are the implementations in Java and C++. Note: To understand optimised code please refer the description given in part 4 below this code

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;  // Number of test cases
    
    while (t--) {
        int n, k;
        string s;
        cin >> n >> k >> s;
        
        int freq[26] = {0};
        for (char c : s) {
            freq[c - 'a']++;
        }

        int oddCount = 0;
        for (int count : freq) {
            if (count % 2 == 1) {
                oddCount++;
            }
        }

        if (oddCount - 1 <= k) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}
          

JAVA

import java.util.*;

public class Chemistry {

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int t = scn.nextInt();  // Number of test cases

        while (t-- > 0) {
            int n = scn.nextInt();      // Length of the string
            int k = scn.nextInt();      // Number of characters to delete
            String s = scn.next();      // Input string
            
            if (solve(n, k, s)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        scn.close();
    }

    private static boolean solve(int n, int k, String s) {
        // Step 1: Count character frequencies
        int[] freq = new int[26];
        for (int i = 0; i < n; i++) {
            freq[s.charAt(i) - 'a']++;
        }

        // Step 2: Count characters with odd frequencies
        int oddCount = 0;
        for (int count : freq) {
            if (count % 2 == 1) {
                oddCount++;
            }
        }

        // Step 3: Check if k deletions are enough
        return (oddCount - 1) <= k;
    }
}
         

What if \( k > \text{oddCount} - 1 \)?

Handling Leftover Deletions for Palindrome Rearrangement

Once we calculate the minimum number of deletions required to make a string valid for a palindrome, we can analyze what happens when there are leftover deletions then still it not affects our answer.

Required Deletions

The required deletions are calculated as:

Required Deletions = oddCount - 1

Where oddCount is the number of characters with odd frequencies.

Leftover Deletions

If the allowed deletions k is greater than oddCount - 1, then we have:

Leftover = k - (oddCount - 1)

Now, we need to analyze what happens when these leftover deletions are even or odd.

Case 1: Leftover Deletions are Even

Deleting an even number of characters from a string that can already be rearranged into a palindrome does not break the palindrome condition.

Why? Deleting an even number of characters maintains the balance between character frequencies:

• If a character’s count is even, deleting two instances still keeps it even.
• If a character’s count is odd, deleting two instances still keeps it odd.

Therefore, deleting even characters will not disrupt the structure of the palindrome.

Example:

oddCount = 3
Required Deletions = 3 - 1 = 2
k = 6
Leftover = 6 - 2 = 4 (even)

Here, we can safely delete 4 more characters (in pairs), and the resulting string will still satisfy the palindrome condition.

Case 2: Leftover Deletions are Odd

If the leftover deletions are odd, we need to handle this carefully. Here’s the approach:

• Delete the Single Odd Character: If there’s one character with an odd frequency (which we kept to allow the palindrome condition), we can delete it to make its frequency even.
• After this, we are left with an even number of leftover deletions.
• Delete Even Characters: Once the single odd character is deleted, the remaining deletions are even. As explained earlier, deleting an even number of characters does not disrupt the palindrome structure.

Example:

oddCount = 5
Required Deletions = 5 - 1 = 4
k = 7
Leftover = 7 - 4 = 3 (odd)

Steps to handle this:

1. Delete the one character with an odd frequency (remaining deletions: 3 - 1 = 2).
2. Now delete 2 more characters (even number), which maintains the palindrome condition.

Why Does This Work?

A palindrome requires at most one character with an odd frequency. By handling leftover deletions carefully:

• If even, we delete characters in pairs to preserve balance.
• If odd, we first delete the one odd character, then delete in pairs.

This guarantees that the resulting string still satisfies the palindrome condition.

Time and Space Complexity

Time Complexity: \( O(n) \) per test case. We iterate over the string once to count frequencies and once to calculate \( \text{oddCount} \).

Space Complexity: \( O(1) \). We use a fixed-size array of 26 elements to store frequencies.

Conclusion

The key insight in this problem is to focus on characters with odd frequencies. By ensuring that \( k \) deletions are enough to reduce the odd frequencies to at most 1, we can efficiently determine if the string can be rearranged into a palindrome.